#include <string>
#include <vector>

using namespace std;

class BIT
{
private:
    vector<int> tree;

public:
    BIT(int n) : tree(n) {}

    void update(int x, int val)
    {
        while(x < tree.size())
        {
            tree[x] += val;
            x += x & -x;
        }
    }

    int query(int x)
    {
        int ret = 0;
        while(x > 0)
        {
            ret += tree[x];
            x &= x - 1;
        }
        return ret;
    }
};

class Solution 
{
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) 
    {
        auto t = new BIT(n + 1);
        for(auto& b : bookings)
        {
            t->update(b[0], b[2]);
            t->update(b[1] + 1, -b[2]);
        }

        vector<int> ret(n);
        for(int i = 1; i <= n; ++i)
        {
            ret[i - 1] = t->query(i);
        }
        return ret;
    }
};

// 2251. 花期内花的数目
class Solution 
{
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) 
    {
        int n = flowers.size();
        vector<int> starts(n), ends(n);
        for(int i = 0; i < n; ++i)
        {
            starts[i] = flowers[i][0];
            ends[i] = flowers[i][1];
        }

        sort(starts.begin(), starts.end());
        sort(ends.begin(), ends.end());

        for(int& p : people)
        {
            p = (upper_bound(starts.begin(), starts.end(), p) - starts.begin()) - 
                (lower_bound(ends.begin(), ends.end(), p) - ends.begin());
        }
        return people;
    }
};